/***************************************************************************************
/
/  File name: UF.h
/
/  Authors:
/           Ilan   Bar Magen  061220380	 ilanbm@t2
/    		Shalev Mintz      066078189  shalevmi@t2  
/
/  Submition date: 6/8/2008
/
/  This file contains:  A generic disjoint Set Class, implementig Union and Find.
/					
****************************************************************************************/


#ifndef UF_H
#define UF_H

#include<cstdlib>  // for NULL
#include<iostream>

using namespace std;

typedef int Elementkey;
typedef int SetKey;
/* The data stracture is a vector in which every Element starts off as a
 * singleton set, meaning it is the set root. when a union accures, the smaller
 * set is merged into the larger set. A root element holds a pointer to the Set data. 
 * in this implementation,
 * Set elements (which are not Set roots) cannot hold additional data. 
 */
template <class D> //D - DataType
class Set
{
public:
	D data;		 
	int size;
	// default C'tor 
	Set(D theData = D(), int theSize = 1):
	data(theData), size(theSize) {}
	// D'tor - done member-wise, no dynamic allocations.
	// same for "Copy C'tor" and "Assign Op'r" 
	~Set() {} 
};

template <class D> //D - DataType
class Element
{
public:	 
	Element *father;	
	Set<D> *set;
	// default C'tor 
	Element(Element* theFather = NULL, Set<D>* theSet = NULL):
	father(theFather), set(theSet) {}

	// D'tor - done member-wise, no dynamic allocations.
	// same for "Copy C'tor" and "Assign Op'r" 
	~Element() {} 
};



template <class D> //D - DataType.
class UF
{
private:
	
	Element<D> *ElementsArray;
	Set<D> *SetArray;
	int sz; 
	Elementkey Find_leader(Elementkey k);
	void intoSet(Elementkey k1, Elementkey k2, bool first); // k2 element is merged into k1

public:
	UF(int n): sz(n) {ElementsArray  = new Element<D>[n];
					  SetArray = new Set<D>[n];
					  for(int i=0;i<n;i++) {
						ElementsArray[i].set = &SetArray[i];
					  }
	}
	~UF() {delete[] ElementsArray; delete[] SetArray;}

	SetKey Find(Elementkey k); //perform a find with path compression
 
	SetKey Union(SetKey k1, SetKey k2); //k1's data will be the new data of the union.
	
	void SetData(SetKey k, D theData);
	bool isSet(SetKey k) { 	return ((k < sz) && (k >= 0) && (SetArray[k].size != 0)); }
	D& RetrieveData(SetKey k)  {return SetArray[k].data;}
	int GetSize(SetKey k) {return SetArray[k].size;}

};


template<class D>
void UF<D>::intoSet(Elementkey k1, Elementkey k2, bool first) // k2 directed into k1, if first then k1' set is the union, else k2's.
{
	
		int add_size = (*ElementsArray[k2].set).size;
		if(!first) { add_size = (*ElementsArray[k1].set).size; 
					(*ElementsArray[k1].set).size = 0;     
					ElementsArray[k1].set = ElementsArray[k2].set; //who is the container set.		     
		} else {
			(*ElementsArray[k2].set).size = 0;   
		}
		(*ElementsArray[k1].set).size += add_size;
		ElementsArray[k2].father = &ElementsArray[k1]; //
	
	ElementsArray[k2].set = NULL; // k2's set is now k1's data. 
	return;
}

template<class D>
Elementkey UF<D>::Find_leader(Elementkey k) //perform a find with path compression
{
	Elementkey root_key = -1;
	if(ElementsArray[k].father == NULL) return k;
	else
	{
		root_key = Find_leader(ElementsArray[k].father - ElementsArray);
		ElementsArray[k].father = &ElementsArray[root_key];
		return root_key;
	}
}


template<class D>
SetKey UF<D>::Find(Elementkey k) //perform a find with path compression
{
	return ElementsArray[Find_leader(k)].set - SetArray;
}



template<class D>
SetKey UF<D>::Union(SetKey k1, SetKey k2)
{
	Elementkey k1leader = Find_leader(k1);
	Elementkey k2leader = Find_leader(k2);
	SetKey k1set = Find(k1);
	SetKey k2set = Find(k2);
	if( k1set != k1 ||  k2set != k2 ) return -1; 
		// if they are not sets.
	
	if(SetArray[k1set].size >= SetArray[k2set].size)
			intoSet(k1leader, k2leader, true);
	else intoSet(k2leader, k1leader, false);
	return k1set;
}

template<class D>
void UF<D>::SetData(SetKey k, D theData)
{
	if(SetArray[k].data == NULL)
		SetArray[k].data = theData;
	return;
}

#endif
